#ifndef SPW_DEQUE_H
#define SPW_DEQUE_H
#include "memory/spw_alloc.h"
#include "iterator/spw_iterator.h"
#include "utility/spw_move_in.h"
#include "algorithm/spw_algo.h"
#include "spw_config.h"
#include "memory/spw_uninitialized.h"
#include "exception/spw_stdexcept.h"
#include <initializer_list>

namespace spwstd {
#define DEQUE_BUF_SIZE 512

// deque buffer 可有元素个数
constexpr spwconfig::size_t dequeBufSize(spwconfig::size_t size) {
    return (size < DEQUE_BUF_SIZE ? spwconfig::size_t(DEQUE_BUF_SIZE/size) : spwconfig::size_t(1));
}

/* DequeIterator_in */
template<typename Tp, typename Ref, typename Ptr>
struct DequeIterator_in {
    using ElemPointer = Tp*;
    using MapPointer = Tp**;

    using Iter = DequeIterator_in<Tp, Tp&, Tp*>;
    using ConstIter = DequeIterator_in<Tp, const Tp&, const Tp*>;
    using DifferType = spwconfig::ptrdiff_t;
    using SizeType = spwconfig::size_t;
    using IteratorCategory = spwstd::BidirectionalIterTag;
    using ValueType = Tp;
    using Pointer = Ptr;
    using Refer = Ref;
    using Self = DequeIterator_in;

    ElemPointer cur_;  // 指向当前元素
    ElemPointer first_; // 该结点buffer起点
    ElemPointer last_; // 该结点buffer尾
    MapPointer node_; // 指向中控器的当前结点

    static spwconfig::size_t BufferSize() { return dequeBufSize(sizeof(Tp)); }

    DequeIterator_in(): cur_{}, first_{}, last_{}, node_{}
    {}

    DequeIterator_in(ElemPointer x, MapPointer y): cur_{x}, first_{*y}, last_{*y+BufferSize()}, node_{y}
    {}

    DequeIterator_in(const Iter& x): cur_{x.cur_}, first_{x.first_}, last_{x.last_}, node_{x.node_}
    {}

    DequeIterator_in& operator=(const DequeIterator_in&) = default;

    Iter ConstCast() const { return Iter(cur_, node_); };
    Refer operator*() const { return *cur_; }
    Pointer operator->() const { return cur_; }

    Self& operator++() {
        ++cur_;
        if (cur_ == last_) {
            SetNode_in(node_ + 1);
            cur_ = first_;
        }
        return *this;
    }

    Self& operator++(int) {
        Self tmp = *this;
        ++*this;
        return tmp;
    }

    Self& operator--() {
        if (cur_ == first_) {
            SetNode_in(node_ - 1);
            cur_ = last_;
        }
        --cur_;
        return *this;
    }

    Self& operator--(int) {
        Self tmp = *this;
        --*this;
        return tmp;
    }

    Self& operator+=(DifferType n) {
        const DifferType offset = n + (cur_ - first_);
        if (offset >= 0 && offset < DifferType(BufferSize()))  {
            cur_ += n;
        } else {
            const DifferType node_offset = offset>0 ? 
                offset / DifferType(BufferSize()) 
                : -DifferType((-offset-1)/BufferSize()) - 1;
            SetNode_in(node_ + node_offset);
            cur_ = first_ + (offset - node_offset*DifferType(BufferSize()));
        }
        return *this;
    }

    Self operator+(DifferType n) const {
        Self tmp = *this;
        return tmp += n;
    }

    Self& operator-=(DifferType n) { return *this += -n; }

    Self operator-(DifferType n) const {
        Self tmp = *this;
        return tmp -= n;
    }

    Refer operator[](DifferType n) const { return *(*this+n); }

    void SetNode_in(MapPointer new_node) {
        node_ = new_node;
        first_ = *new_node;
        last_ = first_ + dequeBufSize(sizeof(Tp));
    }

    bool operator==(const Self& x) const { return cur_ == x.cur_; }
    bool operator!=(const Self& x) const { return cur_ != x.cur_; }
    bool operator<(const Self& x) const { 
        return (node_ == x.node_) ? (cur_<x.cur_) : (node_<x.node_); }
};

template<typename Tp, typename Ref, typename Ptr>
inline typename DequeIterator_in<Tp, Ref, Ptr>::DifferType
operator-(const DequeIterator_in<Tp, Ref, Ptr>& x, 
          const DequeIterator_in<Tp, Ref, Ptr>& y) {
    return typename DequeIterator_in<Tp, Ref, Ptr>::DifferType
        (DequeIterator_in<Tp, Ref, Ptr>::BufferSize())*(x.node_ - y.node_-1)
        + (x.cur_ - x.first_) + (y.last_ - y.cur_);
}

template<typename Tp, typename Ref, typename Ptr>
inline typename DequeIterator_in<Tp, Ref, Ptr>::DifferType
operator+(spwconfig::ptrdiff_t n, 
          const DequeIterator_in<Tp, Ref, Ptr>& x) {
    return x + n;
}

/* DequeBase_in */
template<typename Tp, typename Alloc>
class DequeBase_in {
public:
    using TpAllocType = Alloc;
    using Iter = DequeIterator_in<Tp, Tp&, Tp*>;
    using ConstIter = DequeIterator_in<Tp, const Tp&, const Tp*>;

protected:
    using MapPointer = typename Iter::MapPointer;
    using Ptr = Tp*;
    using ConstPtr = const Tp*;
    using MapAllocType = spwdetail::AllocRebind<Alloc, Ptr>;

    struct DequeImpl_in : public TpAllocType
    {
    public:
        MapPointer map_; // 中控器
        spwconfig::size_t map_size_;
        Iter start_;  // 第一个结点
        Iter finish_; // 最后一个结点

    public:
        DequeImpl_in() : TpAllocType{}, map_{}, map_size_{0}, start_{}, finish_{}
        { }

        DequeImpl_in(DequeImpl_in &&) = default;

        void SwapData(DequeImpl_in &x) {
            using spwstd::spwuti::swap;
            swap(this->start_, x.start_);
            swap(this->finish_, x.finish_);
            swap(this->map_, x.map_);
            swap(this->map_size_, x.map_size_);
        }
    };

protected:
    DequeImpl_in impl_;
    enum { init_map_size = 8};

public:
    TpAllocType GetAlloc() const {
        return *static_cast<TpAllocType*>(&this->impl_);
    }

    DequeBase_in(): impl_{}
    { InitMap_in(0); }

    DequeBase_in(spwconfig::size_t elem_num): impl_{}
    { InitMap_in(elem_num); }

    DequeBase_in(DequeBase_in&& other): impl_{spwuti::move(other.impl_)}
    {
        InitMap_in(0);
        if (other.impl_.map_) {
            this->impl_.SwapData(other.impl_);
        }
    }

    ~DequeBase_in();
protected:
    void InitMap_in(spwconfig::size_t elem_num);
    void CreateNodes_in(MapPointer map_start, MapPointer map_finish);
    void DestroyNodes_in(MapPointer map_start, MapPointer map_finish);
    Ptr AllocNode_in() {
        return AllocInterface<Tp, TpAllocType>::s_allocate(dequeBufSize(sizeof(Tp)));
    }

    void DeallocNode_in(Ptr p) {
        AllocInterface<Tp, TpAllocType>::s_deallocate(p, dequeBufSize(sizeof(Tp)));
    }

    MapPointer AllocMap_in(spwconfig::size_t node_num) {
        return AllocInterface<typename AllocTraits<MapAllocType>::ValueType, MapAllocType>::s_allocate(node_num);
    }

    void DeallocMap_in(MapPointer p, spwconfig::size_t n) {
        AllocInterface<typename AllocTraits<MapAllocType>::ValueType, MapAllocType>::s_deallocate(p, n);
    }
};

/* Deque */
template<typename Tp, typename Alloc=spwstd::DefaultAlloc<Tp>>
class Deque: protected DequeBase_in<Tp, Alloc> {
    using Base = DequeBase_in<Tp, Alloc>;
public:
    using ValueType = Tp;
    using Pointer = Tp*;
    using ConstPointer = const Tp*;
    using Refer = Tp&;
    using ConstRefer = const Tp&;
    using Iter = typename Base::Iter;
    using ConstIter = typename Base::ConstIter;
    using SizeType = spwconfig::size_t;
    using DifferType = spwconfig::ptrdiff_t;
    using AllocT = Alloc;

    Deque(): Base{}{}

    explicit Deque(SizeType n, const ValueType& value=ValueType{})
        : Base{n}
    { FillInit_in(value);}

    Deque(const Deque& other): Base{other.Size()}
    { spwstd::uninitializedCopy(other.Begin(), other.End(), this->impl_.start_); }

    Deque(Deque&& other): Base{spwuti::move(other)}
    {}

    Deque(std::initializer_list<ValueType> l): Base{l.size()}
    { spwstd::uninitializedCopy(l.begin(), l.end(), this->impl_.start_); }

    template<typename InputIter, typename = spwdetail::RequireInputIter<InputIter>>
    Deque(InputIter first, InputIter last): Base{SizeType(last-first)}
    {
        spwstd::uninitializedCopy(first, last, this->impl_.start_);
    }

    ~Deque() {
        DestroyDate_in(Begin(), End());
    }

protected:
    using MapPointer = typename Base::MapPointer;
    using Base::DestroyNodes_in;
    using Base::InitMap_in;
    using Base::CreateNodes_in;
    using Base::DeallocMap_in;
    using Base::DeallocNode_in;

    static spwconfig::size_t BufferSize() { return dequeBufSize(sizeof(Tp)); }
    void FillInit_in(const ValueType& value);
    void DestroyDate_in(Iter first, Iter last);
    void RangeCheck_in(SizeType n) const {
        if (n >= this->Size()) {
            throw spwexcept::OutOfRange("at() out of range");
        }
    }

    // erase [pos, end)
    void EraseAtEnd_in(Iter pos)
    {
        DestroyDate_in(pos, End());
        DestroyNodes_in(pos.node_ + 1, this->impl_.finish_.node_ + 1);
        this->impl_.finish_ = pos;
    }

public:

    /*元素访问*/
    Refer operator[](SizeType n) {
        return this->impl_.start_[DifferType(n)];
    }

    ConstRefer operator[](SizeType n) const {
        return this->impl_.start_[DifferType(n)];
    }

    Refer At(SizeType n) {
        RangeCheck_in(n);
        return (*this)[n];
    }

    ConstRefer At(SizeType n) const {
        RangeCheck_in(n);
        return (*this)[n];
    }

    Refer Front() {
        return *Begin();
    }

    ConstRefer Front() const {
        return *Begin();
    }

    Refer Back() {
        Iter tmp = End();
        --tmp;
        return *tmp;
    }

    ConstRefer Back() const {
        ConstIter tmp = End();
        --tmp;
        return *tmp;
    }

    /*迭代器*/
    Iter Begin() {
        return this->impl_.start_;
    }

    ConstIter Begin() const {
        return this->impl_.start_;
    }

    Iter End() {
        return this->impl_.finish_;
    }

    ConstIter End() const {
        return this->impl_.finish_;
    }

    ConstIter Cbegin() const {
        return this->impl_.start_;
    }

    ConstIter Cend() {
        return this->impl_.finish_;
    }
    /*容量*/

    SizeType Size() const {
        return this->impl_.finish_ - this->impl_.start_; 
    }

    bool Empty() const {
        return this->impl_.finish_ == this->impl_.start_;
    }

    /*修改器insert, emplace, erase, pushback, popback, pushfront, popfront, swap, resize*/
    void Clear();

    void PushBack(const ValueType& value);
    /*
    void PushBack(ValueType&& value);
    void PushFront(const ValueType& value);
    void PushFront(ValueType&& value);
*/
    /*
    Iter Insert(ConstIter pos, const ValueType& x);
    Iter Insert(ConstIter pos, ValueType&& x);
    Iter Insert(ConstIter pos, std::initializer_list<ValueType> l);

    template<typename InputIter, typename = spwdetail::RequireInputIter<InputIter>>
    Iter Insert(ConstIter pos, InputIter first, InputIter last);
    Iter Erase(ConstIter pos);
    Iter Erase(ConstIter first, ConstIter last);
    */
};

/* dequebase func*/
template <typename Tp, typename Alloc>
void Deque<Tp, Alloc>::DestroyDate_in(Iter first, Iter last) {
    for (MapPointer node = first.node_+1; node < last.node_; ++node) {
        Pointer cur = *node;
        for (spwconfig::size_t i=0; i<BufferSize(); ++i, ++cur)
        spwstd::AllocInterface<Tp, Alloc>::s_destroy(cur);
    }

    if (first.node_ != last.node_) {
        Pointer cur = first.cur_;
        for (; cur<first.last_; ++cur) {
            spwstd::AllocInterface<Tp, Alloc>::s_destroy(cur);
        }

        cur = last.first_;
        for (; cur<last.cur_; ++cur) {
            spwstd::AllocInterface<Tp, Alloc>::s_destroy(cur);
        }
    } else {
        Pointer cur = first.cur_;
        for (; cur<last.cur_; ++cur) {
            spwstd::AllocInterface<Tp, Alloc>::s_destroy(cur);
        }
    }
}

template <typename Tp, typename Alloc>
void DequeBase_in<Tp, Alloc>::InitMap_in(spwconfig::size_t elem_num)
{
    const spwconfig::size_t num_node = (elem_num / dequeBufSize(sizeof(Tp)) + 1);
    this->impl_.map_size_  = 
        spwalg::max(spwconfig::size_t(init_map_size), spwconfig::size_t(num_node+2));
    this->impl_.map_ = AllocMap_in(this->impl_.map_size_);

    // map_start 从中间开始
    MapPointer map_start = (this->impl_.map_ + (this->impl_.map_size_ - num_node)/2);
    MapPointer map_finish = map_start + num_node - 1;

    try {
        CreateNodes_in(map_start, map_finish);
    } catch (...) {
        DeallocMap_in(this->impl_.map_, this->impl_.map_size_);
        this->impl_.map_ = MapPointer{};
        this->impl_.map_size_ = 0;
        throw;
    }

    this->impl_.start_.SetNode_in(map_start);
    this->impl_.finish_.SetNode_in(map_finish);
    this->impl_.start_.cur_ = this->impl_.start_.first_;
    this->impl_.finish_.cur_ = this->impl_.finish_.first_ + elem_num % dequeBufSize(sizeof(Tp));
}

template <typename Tp, typename Alloc>
void DequeBase_in<Tp, Alloc>::CreateNodes_in(MapPointer map_start, MapPointer map_finish)
{
    MapPointer cur_;
    try {
        for (cur_ = map_start; cur_ <= map_finish; ++cur_) {
            *cur_ = this->AllocNode_in();
        }
    } catch(...) {
        DestroyNodes_in(map_start, cur_);
        throw;
    }
}

template <typename Tp, typename Alloc>
void DequeBase_in<Tp, Alloc>::DestroyNodes_in(MapPointer map_start, MapPointer map_finish)
{
    for (MapPointer n = map_start; n < map_finish; ++n) {
        DeallocNode_in(*n);
    }
}

template <typename Tp, typename Alloc>
DequeBase_in<Tp, Alloc>::~DequeBase_in() {
    if (this->impl_.map_) {
        DestroyNodes_in(this->impl_.start_.node_, this->impl_.finish_.node_+1);
        DeallocMap_in(this->impl_.map_, this->impl_.map_size_);
    }
}

/*deque func*/
template <typename Tp, typename Alloc>
void Deque<Tp, Alloc>::FillInit_in(const ValueType& value) {
    MapPointer cur;
    try {
        for(cur = this->impl_.start_.node_; cur < this->impl_.finish_.node_; ++cur) {
            spwstd::uninitializedFill(*cur, *cur+BufferSize(), value);
        }
        spwstd::uninitializedFill(this->impl_.finish_.first_, this->impl_.finish_.cur_, value);
    } catch(...) {
        this->DestroyNodes_in(this->impl_.start_.node_, cur);
        throw;
    }
}

/*
template <typename Tp, typename Alloc>
typename Deque<Tp, Alloc>::Iter 
Deque<Tp, Alloc>::Erase(ConstIter c_pos) {
    Iter pos = c_pos->ConstCast();
}
*/

template <typename Tp, typename Alloc>
void Deque<Tp, Alloc>::PushBack(const ValueType& value) {
    if (this->impl_.finish_.cur_ != this->impl_.finish_.last_ - 1) 
    {
        spwstd::AllocInterface<Tp, Alloc>::s_construct(this->impl_.finish_.cur_, value);
        ++this->impl_.finish_.cur_;
    } else {
        // TODO: 完成
        // PushBackAux(value);
        throw; 
    }
}

template <typename Tp, typename Alloc>
void Deque<Tp, Alloc>::Clear()
{ EraseAtEnd_in(Begin()); }

/*
template <typename Tp, typename Alloc>
typename Deque<Tp, Alloc>::Iter 
Deque<Tp, Alloc>::Insert(ConstIter pos, const ValueType& x)
{}
*/
} // namespace spwstd
#endif // SPW_DEQUE_H
